
//27. 移除元素  https://leetcode.cn/problems/remove-element/
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int index = 0; //[0,index-1)就是满足的，新满足的元素放在index位置,然后index++
        int cur = 0;
        for(int i = 0;i<nums.size();i++)
        {
            if(nums[i] != val)
                nums[index++] = nums[i];
        }
        return index;
    }
};
//写法2：
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int index = -1;//当前满足的边界    [0,index]就是满足的
        int cur = 0;
        for(int i = 0;i<nums.size();i++)
        {
            if(nums[i] != val)
                nums[++index] = nums[i];
        }
        //[0,index]就是满足的
        return index+1;//右边界+1就是个数
    }
};

//88. 合并两个有序数组 https://leetcode.cn/problems/merge-sorted-array/
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int total = nums1.size()-1;
        int end1 = m-1;
        int end2 = n-1;
        while(end1>=0&&end2>=0)
        {
            if(nums1[end1] > nums2[end2])
                nums1[total--] = nums1[end1--];
            else
                nums1[total--] = nums2[end2--];
        }
        while(end2>=0)
        {
            nums1[total--] = nums2[end2--];
        }
    }
};

//26. 删除有序数组中的重复项    https://leetcode.cn/problems/remove-duplicates-from-sorted-array/
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int index = 0;
        int cur = 1;
        for(int i = 0;i<nums.size();i++)
        {
            if(nums[i] != nums[index])
                nums[++index] = nums[i];
        }
        //[0,index]
        return index+1;
    }
};

//https://leetcode.cn/problems/remove-duplicates-from-sorted-array-ii/  80. 删除有序数组中的重复项 II
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.size() == 1)
            return 1;
        int index = 2;
        for(int i = 2;i<nums.size();i++)
        {
            if(nums[i] != nums[index-2])
                nums[index++] = nums[i];
        }
        //[0,index)
        return index;
    }
};

//https://leetcode.cn/problems/rotate-array/    189. 轮转数组
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        k %= nums.size();
        reverse(nums.begin(),nums.end());//整体逆置
        reverse(nums.begin(),nums.begin()+k);//前k个数逆置 [0,k)
        reverse(nums.begin()+k,nums.end()); //后n-k个数逆置
    }
};

//225. 用队列实现栈 https://leetcode.cn/problems/implement-stack-using-queues/
class MyStack {
public:
    MyStack() {

    }
    queue<int> q1;//不为空的队列
    queue<int> q2;
    void push(int x) {
        q1.push(x);
    }
    
    int pop() {
        while(q1.size()>1)
        {
            q2.push(q1.front());
            q1.pop();
        }
        int ans = q1.front();
        q1.pop();
        q1.swap(q2);
        return ans;
    }
    
    int top() {
        return q1.back();
    }
    
    bool empty() {
        return q1.empty();
    }
};

//一个队列实现栈
class MyStack {
public:
    MyStack() {

    }
    queue<int> q;
    void push(int x) {
        q.push(x);
    }
    
    int pop() {
        int size = q.size();
        int back = q.back();
        while(--size)
        {
            int front = q.front();
            q.pop();
            q.push(front);
        }
        q.pop();
        return back;
    }
    
    int top() {
        return q.back();
    }
    
    bool empty() {
        return q.empty();
    }
};


//https://leetcode.cn/problems/design-circular-queue/   622. 设计循环队列

//数组实现循环队列
class MyCircularQueue {
public:
    vector<int> v;
    int tail = 0;
    int front = 0;
    int total = 0;
    MyCircularQueue(int k) 
    {
        total = k;
        v.resize(k+1,0);
    }
    
    bool enQueue(int value) {
        if(isFull())
            return false;
        v[tail++] =value;
        tail %= (total+1);
        return true;
    }
    
    bool deQueue() {
        if(isEmpty())
            return false;
        front++;
        front %= (total+1);
        return true;
    }
    
    int Front() {
        if(isEmpty())
            return -1;
        return v[front];
    }
    
    int Rear() {
        if(isEmpty())
            return -1;
        if(tail -1 == -1)
            return v[total];
        else
            return v[tail-1];

    }
    
    bool isEmpty() {
        return front == tail;
    }
    
    bool isFull() {
        return (tail+1)  % (total+1) == front;
    }
};

//链表实现循环队列
class MyCircularQueue {
public:
    struct ListNode
    {
        ListNode* next;
        int val;
        ListNode(int v)
            :val(v),next(nullptr)
        {}
    };
    ListNode* front = nullptr;
    ListNode* tail = nullptr;
    MyCircularQueue(int k) {
        ListNode* head = new ListNode(0);
        tail = head;
        while(k--)
        {
            ListNode* newnode = new ListNode(0);
            tail->next = newnode;
            tail = newnode;
        }
        tail -> next = head;
        front = head;
        tail = head;
    }
    
    bool enQueue(int value) {
        if(isFull())
            return false;
        tail->val = value;
        tail = tail->next;
        return true;
    }
    
    bool deQueue() {
        if(isEmpty())
            return false;
        front = front->next;
        return true;
    }
    
    int Front() {
        if(isEmpty())
            return -1;
        return front->val;
    }
    
    int Rear() {
        if(isEmpty())
            return -1;
        ListNode* cur = front;
        while(cur->next != tail)
            cur = cur->next;
        return cur->val;
    }
    
    bool isEmpty() {
        return front == tail;
    }
    
    bool isFull() {
        return tail->next == front;
    }
};



//232. 用栈实现队列 https://leetcode.cn/problems/implement-queue-using-stacks/
class MyQueue {
public:
    MyQueue() {

    }
    stack<int> Pushst;
    stack<int> Popst;
    void push(int x) {
        Pushst.push(x);
    }
    void check()
    {
        if(Popst.empty())
        {
            while(!Pushst.empty())
            {
                Popst.push(Pushst.top());
                Pushst.pop();
            }
        }
    }
    int pop() {
        check();
        int top = Popst.top();
        Popst.pop();
        return top;
    }
    
    int peek() {
        check();
        return Popst.top();
    }
    
    bool empty() {
        return Popst.empty() && Pushst.empty();
    }
};


//BM41 输出二叉树的右视图   https://www.nowcoder.com/practice/c9480213597e45f4807880c763ddd5f0

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     * @param xianxu int整型vector 先序遍历
     * @param zhongxu int整型vector 中序遍历
     * @return int整型vector
     */
    TreeNode* buildTree(vector<int>& preOrder, int preStart,int preEnd,vector<int>& inOrder,int inStart,int inEnd)
    {
        if(preStart>preEnd || inStart > inEnd)
            return nullptr;
        TreeNode* root = new TreeNode(preOrder[preStart]);
        int index = inStart;
        while(inOrder[index] != preOrder[preStart])
            index++;
        //[inStart,index-1]index[index+1,inEnd]
        //[preStart+1,x]  x-preStart-1 + 1 = index-1+1-instart ==>x = index+-instart+preStart
        //[preStart+1,x][x+1,preEnd]
        int x = index+-inStart+preStart;
        root->left = buildTree(preOrder,preStart+1,x,inOrder,inStart,index-1);
        root->right = buildTree(preOrder,x+1,preEnd,inOrder,index+1,inEnd);
        return root;
    }
    vector<int> solve(vector<int>& preOrder, vector<int>& inOrder) {
        // write code here
        TreeNode* root = buildTree(preOrder,0,preOrder.size(),inOrder,0,inOrder.size()-1);
        queue<TreeNode*> q;
        vector<int> ans;
        q.push(root);
        while(!q.empty())
        {
            int size = q.size();
            for(int i = 0;i<size;i++)
            {
                TreeNode* front = q.front();
                q.pop();
                if(i == size-1)
                    ans.push_back(front->val);
                if(front->left)     q.push(front->left);
                if(front->right)    q.push(front->right);
            }
        }
        return ans;
    }
};

//写法2：
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     * @param xianxu int整型vector 先序遍历
     * @param zhongxu int整型vector 中序遍历
     * @return int整型vector
     */
    TreeNode* buildTree(vector<int>& preOrder, int& prei,vector<int>& inOrder,int inStart,int inEnd)
    {
        if(inStart > inEnd)
            return nullptr;
        TreeNode* root = new TreeNode(preOrder[prei]);
        int index = inStart;
        while(inOrder[index] != preOrder[prei])
            index++;
        prei++;
        root->left = buildTree(preOrder,prei,inOrder,inStart,index-1);
        root->right = buildTree(preOrder,prei,inOrder,index+1,inEnd);
        return root;
    }
    vector<int> solve(vector<int>& preOrder, vector<int>& inOrder) {
        // write code here
        int prei = 0;
        TreeNode* root = buildTree(preOrder,prei,inOrder,0,inOrder.size()-1);
        queue<TreeNode*> q;
        vector<int> ans;
        q.push(root);
        while(!q.empty())
        {
            int size = q.size();
            for(int i = 0;i<size;i++)
            {
                TreeNode* front = q.front();
                q.pop();
                if(i == size-1)
                    ans.push_back(front->val);
                if(front->left)     q.push(front->left);
                if(front->right)    q.push(front->right);
            }
        }
        return ans;
    }
};